package com.xmg.dataStructure.tree;

/**
 * 计算二叉树的最小深度
 */
public class MinTreeDeep {

    public static void main(String[] args) {
        BinTree tree = new BinTree();

        tree.add(2);
        tree.add(1);

        tree.add(3);
        tree.add(4);
        tree.add(5);
        tree.infixOrder();

        System.out.println(getMaxDeep(tree.getRoot()));
    }

    public static int getMinDeep(TreeNode node){
        if (node == null){
            return 0;
        }
        if(node.left==null || node.right==null){
            return 1;
        }
        if(node.left==null){
            return getMinDeep(node.right) + 1;
        }
        if(node.right==null){
            return getMinDeep(node.left) + 1;
        }
        return Math.min(getMinDeep(node.left),getMinDeep(node.right));
    }

    public static int getMaxDeep(TreeNode root){
        if(root==null){
            return 0;
        }
        return max(root,0);
    }
    private static int max(TreeNode node,int depth){
        if(node==null){
            return depth;
        }
        depth++;
        return Math.max(max(node.left,depth),max(node.right,depth));
    }
}

//创建二叉排序树
class BinTree {
    private TreeNode root;

    public TreeNode getRoot() {
        return root;
    }

    public void add(int value) {

        if (root == null) {
            root = new TreeNode(value);
        } else {
            root.add(new TreeNode(value));
        }
    }

    public void infixOrder(){
        root.infixOrder();
    }
}

class TreeNode{
    int value;
    TreeNode left;
    TreeNode right;
    TreeNode(int x){
        value = x;
    }


    public void add(TreeNode node){
        if(node==null){
            return;
        }

        if(node.value<this.value){//向左遍历添加
            if(this.left==null){
                this.left = node;
            }else{
                this.left.add(node);
            }
        }else{//向右遍历添加
            if(this.right==null){
                this.right = node;
            }else{
                this.right.add(node);
            }
        }
    }

    public void infixOrder(){
        if(this.left!=null){
            this.left.infixOrder();
        }
        System.out.println(this);
        if(this.right!=null){
            this.right.infixOrder();
        }
    }

    @Override
    public String toString() {
        return "TreeNode{" +
                "value=" + value +
                '}';
    }
}
